package problem909;

import java.util.LinkedList;
import java.util.Queue;

//909.蛇梯棋
//https://leetcode.cn/problems/snakes-and-ladders/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    int n = 0;
    public int snakesAndLadders(int[][] board) {
        n = board.length;
        if (n < 3)
            return 1;
        boolean[] st = new boolean[n * n + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        st[1] = true;
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int cur = queue.poll();
                if (cur == n * n)  return step;
                System.out.print(cur + " ");
                int[] t = getPos(cur);
                int x = t[0], y = t[1];
                //存在蛇或梯子
                if (board[x][y] != -1) {
                    int tmp = board[x][y];
                    if (tmp == n * n) return step;
                    for (int i = 1; i <= 6 && tmp + i <= n * n; i++) {
                        if (!st[tmp + i]) {
                            queue.add(tmp + i);
                            st[tmp + i] = true;
                        }
                    }
                } else {
                    for (int i = 1; i <= 6 && cur + i <= n * n; i++) {
                        if (!st[cur + i]) {
                            queue.add(cur + i);
                            st[cur + i] = true;
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }

    private int[] getPos(int cur) {
        cur--;
        // 定位cur是在哪一行
        int y = n - 1 - cur / n;
        // n-1-y 为偶数为正序
        // n-1-y 为奇数为逆序
        int x = 0;
        if ((n - 1 - y) % 2 == 0) {
            x = cur % n;
        } else {
            x = n - (cur % n) - 1;
        }
        return new int[] { y, x };
    }
}